package DataStructures.Stack;

/**
 * @author ：ALi
 * @date ：Created in 2021/11/6 20:12
 * @description：递归+回溯解决迷宫问题
 * @modified By：
 * @version: $
 */
public class maze {
    public static void main(String[] args){

        int[][] map = new int[7][6];
        /**
         * 生成数组 1是墙，0是路
         */
        for (int i = 0;i<map.length;i++){
            for (int j = 0;j<map[i].length;j++){
                if(i == 0 || i == map.length-1 || j == 0 || j == map[i].length-1){
                    map[i][j] = 1;
                }else {
                    map[i][j] = 0;
                }
            }
        }
        map[3][1] = 1;
        map[3][2] = 1;

        /**
         * 1 1 1 1 1 1
         * 1 0 0 0 0 1
         * 1 0 0 0 0 1
         * 1 1 1 0 0 1
         * 1 0 0 0 0 1
         * 1 0 0 0 0 1
         * 1 1 1 1 1 1
         */

        setWay(map,1,1);

        for (int i = 0;i<map.length;i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        /**
         * 1 1 1 1 1 1
         * 1 2 0 0 0 1
         * 1 2 2 2 0 1
         * 1 1 1 2 0 1
         * 1 0 0 2 0 1
         * 1 0 0 2 2 1
         * 1 1 1 1 1 1
         */

    }

    /**
     * 规则是从（1,1）到（6,5）下->右->左->上
     * @param map 地图
     * @param i 起点横坐标
     * @param j 起点纵坐标
     * @return true为找到路了.1是墙，0是未走过，2是通的，3是不通
     */
    public static boolean setWay(int[][] map,int i,int j){
        if(map[5][4] == 2){
            return true;
        }
        if(map[i][j] == 0){
            map[i][j] = 2;//将该点假设为通的，则先向下走，通则返回true，不通就向右走，
                         // 不通再向左走，不通就向上走，再不通就将改点设置为3并返回false
            if(setWay(map,i+1,j)){
                return true;
            }else if(setWay(map,i,j+1)){
                return true;
            }else if(setWay(map,i,j-1)){
                return true;
            }else if(setWay(map,i-1,j)){
                return true;
            }else {
                map[i][j] = 3;
                return false;
            }
        }else { //1,2,3的情况中，1是墙，3是不通就返回false，
                // 但是2的情况是，该路走过了，又走回来了，说明改点也是不通的
            return false;
        }


    }



}